package cn.z2huo.algorithm.sort.swapSort.quickSort;

//快速排序
//11,13,2,34,55,9,44,122,32,2,9
public class SortQuick {
	public int swap(int[] array, int low, int high) {
		int central = 0;	//轴值
		int cenPos = 0;		//轴位置
		
		cenPos = low;
		central = array[cenPos];
		while(low < high) {
			while(low < high && array[high] >= central) {
				high --;
			}
			if(low < high) {
				int temp = array[high];
				array[high] = array[low];
				array[low] = temp;
				low ++;
			}
			while(low < high && array[low] <= central) {
				low ++;
			}
			if(low < high) {
				int temp = array[high];
				array[high] = array[low];
				array[low] = temp;
				high --;
			}
		}
		
		low = cenPos;
		return low;
	}
	
	public void quickSort(int[] array, int low, int high) {
		int cenPos = 0;
		if(low < high) {
			cenPos = swap(array, low, high);
			quickSort(array, low, cenPos-1);
			quickSort(array, cenPos+1, high);
		}
		for(int i=0; i<array.length; i++) {
			System.out.printf("%d ",array[i]);
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		int[] array = {11,13,2,34,55,9,44,122,32,2,9};
		SortQuick sq = new SortQuick();
		sq.quickSort(array, 0, array.length-1);
	}
}